Infinity = float('inf')

def bellman_ford(G, w, s):
	S = {}
	P = {}

	# Start step
	for r in G.vertices:
		r.key = Infinity
		P[r] = None
	s.key = 0

	# Relaxing edges
	for i in range(1, len(G.vertices)):
		for u in G.vertices:
			for v in G.adjacencies(u):
				if v.key > u.key + w((u,v)):
					v.key = u.key + w((u,v))
					P[v] = u
			

	# Looking for negatives cycles
	for u in G.vertices:
		for v in G.adjacencies(u):
			if u.key + w((u, v)) < v.key:
				raise Exception('Negative cycle found!')

	# Mounting path from s to each vertex in graph G
	for u in G.vertices:
		v = u
		path = []
		while P[v] is not None:
			path.append(v)
			v = P[v]
		S[u] = path

	return S
